<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>第 6 节 深入理解递归-3 | 算法不好玩</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/book/logo.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="">
    
    <link rel="preload" href="/book/assets/css/0.styles.e159a327.css" as="style"><link rel="preload" href="/book/assets/js/app.a4355b0d.js" as="script"><link rel="preload" href="/book/assets/js/2.ba785ee6.js" as="script"><link rel="preload" href="/book/assets/js/32.aac9aa62.js" as="script"><link rel="prefetch" href="/book/assets/js/10.b6950be1.js"><link rel="prefetch" href="/book/assets/js/11.f4ee7d6e.js"><link rel="prefetch" href="/book/assets/js/12.50fe1ace.js"><link rel="prefetch" href="/book/assets/js/13.42356fcc.js"><link rel="prefetch" href="/book/assets/js/14.e740c742.js"><link rel="prefetch" href="/book/assets/js/15.05c628f7.js"><link rel="prefetch" href="/book/assets/js/16.bd9bc9d5.js"><link rel="prefetch" href="/book/assets/js/17.e120b4fc.js"><link rel="prefetch" href="/book/assets/js/18.398213f8.js"><link rel="prefetch" href="/book/assets/js/19.e29ad0b2.js"><link rel="prefetch" href="/book/assets/js/20.14e30c1c.js"><link rel="prefetch" href="/book/assets/js/21.4f05f6c9.js"><link rel="prefetch" href="/book/assets/js/22.98fbf199.js"><link rel="prefetch" href="/book/assets/js/23.285387f4.js"><link rel="prefetch" href="/book/assets/js/24.852addbe.js"><link rel="prefetch" href="/book/assets/js/25.d30ade13.js"><link rel="prefetch" href="/book/assets/js/26.23dfa040.js"><link rel="prefetch" href="/book/assets/js/27.b6eae7df.js"><link rel="prefetch" href="/book/assets/js/28.97878b08.js"><link rel="prefetch" href="/book/assets/js/29.7217a3d0.js"><link rel="prefetch" href="/book/assets/js/3.f0c15194.js"><link rel="prefetch" href="/book/assets/js/30.0ced5a5a.js"><link rel="prefetch" href="/book/assets/js/31.8f432033.js"><link rel="prefetch" href="/book/assets/js/33.db835477.js"><link rel="prefetch" href="/book/assets/js/34.a1a59c2a.js"><link rel="prefetch" href="/book/assets/js/35.ed2ef96b.js"><link rel="prefetch" href="/book/assets/js/36.48099c55.js"><link rel="prefetch" href="/book/assets/js/37.32827612.js"><link rel="prefetch" href="/book/assets/js/38.58abec0e.js"><link rel="prefetch" href="/book/assets/js/39.f6eb3874.js"><link rel="prefetch" href="/book/assets/js/4.13ea3b32.js"><link rel="prefetch" href="/book/assets/js/40.80523ed8.js"><link rel="prefetch" href="/book/assets/js/41.f7b72b7a.js"><link rel="prefetch" href="/book/assets/js/42.44e40de9.js"><link rel="prefetch" href="/book/assets/js/43.065f077f.js"><link rel="prefetch" href="/book/assets/js/44.386d9aea.js"><link rel="prefetch" href="/book/assets/js/45.d8a88f16.js"><link rel="prefetch" href="/book/assets/js/46.33bc2083.js"><link rel="prefetch" href="/book/assets/js/47.e7767237.js"><link rel="prefetch" href="/book/assets/js/48.9bb76138.js"><link rel="prefetch" href="/book/assets/js/49.c2ca5c29.js"><link rel="prefetch" href="/book/assets/js/5.32eda204.js"><link rel="prefetch" href="/book/assets/js/50.1242fe24.js"><link rel="prefetch" href="/book/assets/js/51.e8f8117d.js"><link rel="prefetch" href="/book/assets/js/52.eae5648f.js"><link rel="prefetch" href="/book/assets/js/53.39876d83.js"><link rel="prefetch" href="/book/assets/js/6.1c662163.js"><link rel="prefetch" href="/book/assets/js/7.29470445.js"><link rel="prefetch" href="/book/assets/js/8.814b737f.js"><link rel="prefetch" href="/book/assets/js/9.d4211262.js">
    <link rel="stylesheet" href="/book/assets/css/0.styles.e159a327.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container no-sidebar"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/book/" class="home-link router-link-active"><!----> <span class="site-name">算法不好玩</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <!----> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="第-6-节-深入理解递归-3"><a href="#第-6-节-深入理解递归-3" class="header-anchor">#</a> 第 6 节 深入理解递归-3</h1> <p>上一节我们例举了链表中既可以使用递归，也可以使用循环解决的两个问题，并且比较了它们的具体实现上的细节。这一节我们以「力扣」第 105 题为例，向大家展示「递归」函数在解决「树」的问题中的应用，第 105 题迭代的解法作为拓展视野的解法，如果觉得不太好理解，可以暂时跳过。</p> <p>我们在这里要向大家指出：在「力扣」上绝大多数「树」和「图」的问题，其实我们都只需要把树结构和图结构看一遍，在看的过程中记录有用的信息就可以了。<strong>所谓看一遍，就是执行一次「深度优先遍历」，因此这些问题绝大多数情况下都可以使用「递归」解决</strong>，因此练习「树」标签的问题可以帮助我们理解递归、掌握递归函数的编写。</p> <h2 id="树的问题绝大多数都可以使用「分治思想」解决"><a href="#树的问题绝大多数都可以使用「分治思想」解决" class="header-anchor">#</a> 树的问题绝大多数都可以使用「分治思想」解决</h2> <h3 id="例-「力扣」第-105-题-从前序与中序遍历序列构造二叉树"><a href="#例-「力扣」第-105-题-从前序与中序遍历序列构造二叉树" class="header-anchor">#</a> 例：「力扣」第 105 题：从前序与中序遍历序列构造二叉树</h3> <p>根据一棵树的前序遍历与中序遍历构造二叉树。</p> <p><strong>注意:</strong>
你可以假设树中没有重复的元素。</p> <p>例如，给出</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>返回如下的二叉树：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>    3
   / \
  9  20
    /  \
   15   7
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h3 id="📺视频题解"><a href="#📺视频题解" class="header-anchor">#</a> 📺视频题解</h3> <p><img src="96352760-d012-4677-8631-c77e23687479" alt="...从前序与中序遍历序列构造二叉树.mp4"></p> <h3 id="📖文字题解"><a href="#📖文字题解" class="header-anchor">#</a> 📖文字题解</h3> <h4 id="前言"><a href="#前言" class="header-anchor">#</a> 前言</h4> <p>二叉树前序遍历的顺序为：</p> <ul><li><p>先遍历根节点；</p></li> <li><p>随后递归地遍历左子树；</p></li> <li><p>最后递归地遍历右子树。</p></li></ul> <p>二叉树中序遍历的顺序为：</p> <ul><li><p>先递归地遍历左子树；</p></li> <li><p>随后遍历根节点；</p></li> <li><p>最后递归地遍历右子树。</p></li></ul> <p>在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。</p> <h4 id="方法一-递归"><a href="#方法一-递归" class="header-anchor">#</a> 方法一：递归</h4> <p><strong>思路</strong></p> <p>对于任意一颗树而言，前序遍历的形式总是</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p>即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><p>只要我们在中序遍历中<strong>定位</strong>到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有<strong>左右括号</strong>进行定位。</p> <p>这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。</p> <p><strong>细节</strong></p> <p>在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mn class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 的时间对根节点进行定位了。</p> <p>下面的代码给出了详细的注释。</p> <div class="language-C++ [sol1-C++] line-numbers-mode"><pre class="language-text"><code>class Solution {
private:
    unordered_map&lt;int, int&gt; index;

public:
    TreeNode* myBuildTree(const vector&lt;int&gt;&amp; preorder, const vector&lt;int&gt;&amp; inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left &gt; preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root-&gt;left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root-&gt;right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector&lt;int&gt;&amp; preorder, vector&lt;int&gt;&amp; inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i &lt; n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br></div></div><div class="language-Java [sol1-Java] line-numbers-mode"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">private</span> <span class="token class-name">Map</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">,</span> <span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> indexMap<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">TreeNode</span> <span class="token function">myBuildTree</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> preorder<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> inorder<span class="token punctuation">,</span> <span class="token keyword">int</span> preorder_left<span class="token punctuation">,</span> <span class="token keyword">int</span> preorder_right<span class="token punctuation">,</span> <span class="token keyword">int</span> inorder_left<span class="token punctuation">,</span> <span class="token keyword">int</span> inorder_right<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>preorder_left <span class="token operator">&gt;</span> preorder_right<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 前序遍历中的第一个节点就是根节点</span>
        <span class="token keyword">int</span> preorder_root <span class="token operator">=</span> preorder_left<span class="token punctuation">;</span>
        <span class="token comment">// 在中序遍历中定位根节点</span>
        <span class="token keyword">int</span> inorder_root <span class="token operator">=</span> indexMap<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>preorder<span class="token punctuation">[</span>preorder_root<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        
        <span class="token comment">// 先把根节点建立出来</span>
        <span class="token class-name">TreeNode</span> root <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>preorder<span class="token punctuation">[</span>preorder_root<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 得到左子树中的节点数目</span>
        <span class="token keyword">int</span> size_left_subtree <span class="token operator">=</span> inorder_root <span class="token operator">-</span> inorder_left<span class="token punctuation">;</span>
        <span class="token comment">// 递归地构造左子树，并连接到根节点</span>
        <span class="token comment">// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素</span>
        root<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token function">myBuildTree</span><span class="token punctuation">(</span>preorder<span class="token punctuation">,</span> inorder<span class="token punctuation">,</span> preorder_left <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> preorder_left <span class="token operator">+</span> size_left_subtree<span class="token punctuation">,</span> inorder_left<span class="token punctuation">,</span> inorder_root <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 递归地构造右子树，并连接到根节点</span>
        <span class="token comment">// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素</span>
        root<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token function">myBuildTree</span><span class="token punctuation">(</span>preorder<span class="token punctuation">,</span> inorder<span class="token punctuation">,</span> preorder_left <span class="token operator">+</span> size_left_subtree <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> preorder_right<span class="token punctuation">,</span> inorder_root <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> inorder_right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> root<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token class-name">TreeNode</span> <span class="token function">buildTree</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> preorder<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> inorder<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> n <span class="token operator">=</span> preorder<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
        <span class="token comment">// 构造哈希映射，帮助我们快速定位根节点</span>
        indexMap <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">,</span> <span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            indexMap<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span>inorder<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> <span class="token function">myBuildTree</span><span class="token punctuation">(</span>preorder<span class="token punctuation">,</span> inorder<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br></div></div><div class="language-Python [sol1-Python3] line-numbers-mode"><pre class="language-python"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">buildTree</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> preorder<span class="token punctuation">:</span> List<span class="token punctuation">[</span><span class="token builtin">int</span><span class="token punctuation">]</span><span class="token punctuation">,</span> inorder<span class="token punctuation">:</span> List<span class="token punctuation">[</span><span class="token builtin">int</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">&gt;</span> TreeNode<span class="token punctuation">:</span>
        <span class="token keyword">def</span> <span class="token function">myBuildTree</span><span class="token punctuation">(</span>preorder_left<span class="token punctuation">:</span> <span class="token builtin">int</span><span class="token punctuation">,</span> preorder_right<span class="token punctuation">:</span> <span class="token builtin">int</span><span class="token punctuation">,</span> inorder_left<span class="token punctuation">:</span> <span class="token builtin">int</span><span class="token punctuation">,</span> inorder_right<span class="token punctuation">:</span> <span class="token builtin">int</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> preorder_left <span class="token operator">&gt;</span> preorder_right<span class="token punctuation">:</span>
                <span class="token keyword">return</span> <span class="token boolean">None</span>
            
            <span class="token comment"># 前序遍历中的第一个节点就是根节点</span>
            preorder_root <span class="token operator">=</span> preorder_left
            <span class="token comment"># 在中序遍历中定位根节点</span>
            inorder_root <span class="token operator">=</span> index<span class="token punctuation">[</span>preorder<span class="token punctuation">[</span>preorder_root<span class="token punctuation">]</span><span class="token punctuation">]</span>
            
            <span class="token comment"># 先把根节点建立出来</span>
            root <span class="token operator">=</span> TreeNode<span class="token punctuation">(</span>preorder<span class="token punctuation">[</span>preorder_root<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token comment"># 得到左子树中的节点数目</span>
            size_left_subtree <span class="token operator">=</span> inorder_root <span class="token operator">-</span> inorder_left
            <span class="token comment"># 递归地构造左子树，并连接到根节点</span>
            <span class="token comment"># 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素</span>
            root<span class="token punctuation">.</span>left <span class="token operator">=</span> myBuildTree<span class="token punctuation">(</span>preorder_left <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> preorder_left <span class="token operator">+</span> size_left_subtree<span class="token punctuation">,</span> inorder_left<span class="token punctuation">,</span> inorder_root <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token comment"># 递归地构造右子树，并连接到根节点</span>
            <span class="token comment"># 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素</span>
            root<span class="token punctuation">.</span>right <span class="token operator">=</span> myBuildTree<span class="token punctuation">(</span>preorder_left <span class="token operator">+</span> size_left_subtree <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> preorder_right<span class="token punctuation">,</span> inorder_root <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> inorder_right<span class="token punctuation">)</span>
            <span class="token keyword">return</span> root
        
        n <span class="token operator">=</span> <span class="token builtin">len</span><span class="token punctuation">(</span>preorder<span class="token punctuation">)</span>
        <span class="token comment"># 构造哈希映射，帮助我们快速定位根节点</span>
        index <span class="token operator">=</span> <span class="token punctuation">{</span>element<span class="token punctuation">:</span> i <span class="token keyword">for</span> i<span class="token punctuation">,</span> element <span class="token keyword">in</span> <span class="token builtin">enumerate</span><span class="token punctuation">(</span>inorder<span class="token punctuation">)</span><span class="token punctuation">}</span>
        <span class="token keyword">return</span> myBuildTree<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br></div></div><div class="language-golang [sol1-Golang] line-numbers-mode"><pre class="language-text"><code>func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &amp;TreeNode{preorder[0], nil, nil}
    i := 0
    for ; i &lt; len(inorder); i++ {
        if inorder[i] == preorder[0] {
            break
        }
    }
    root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
    root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
    return root
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><p><strong>复杂度分析</strong></p> <ul><li><p>时间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，其中 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 是树中的节点个数。</p></li> <li><p>空间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，除去返回的答案需要的 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 空间之外，我们还需要使用 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 的空间存储哈希映射，以及 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>（其中 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi></mjx-math></mjx-container> 是树的高度）的空间表示递归时栈空间。这里 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="&lt;"></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>，所以总空间复杂度为 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</p></li></ul> <h4 id="方法二-迭代"><a href="#方法二-迭代" class="header-anchor">#</a> 方法二：迭代</h4> <p><strong>思路</strong></p> <p>迭代法是一种非常巧妙的实现方法。</p> <p>对于前序遍历中的任意两个连续节点 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 和 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container>，根据前序遍历的流程，我们可以知道 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 和 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container> 只有两种可能的关系：</p> <ul><li><p><mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container> 是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 的左儿子。这是因为在遍历到 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 之后，下一个遍历的节点就是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 的左儿子，即 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container>；</p></li> <li><p><mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 没有左儿子，并且 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container> 是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 的某个祖先节点（或者 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 本身）的右儿子。如果 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 没有左儿子，那么下一个遍历的节点就是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 的右儿子。如果 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi></mjx-math></mjx-container> 不在它的右儿子的子树中）的节点 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msub><mjx-mi noIC="true" class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.15em;"><mjx-mi size="s" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-script></mjx-msub></mjx-math></mjx-container>，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="v"></mjx-c></mjx-mi></mjx-math></mjx-container> 就是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msub><mjx-mi noIC="true" class="mjx-i"><mjx-c c="u"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.15em;"><mjx-mi size="s" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-script></mjx-msub></mjx-math></mjx-container> 的右儿子。</p></li></ul> <p>第二种关系看上去有些复杂。我们举一个例子来说明其正确性，并在例子中给出我们的迭代算法。</p> <p><strong>例子</strong></p> <p>我们以树</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><p>为例，它的前序遍历和中序遍历分别为</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>我们用一个栈 <code>stack</code> 来维护「当前节点的所有还没有考虑过右儿子的祖先节点」，栈顶就是当前节点。也就是说，只有在栈中的节点才可能连接一个新的右儿子。同时，我们用一个指针 <code>index</code> 指向中序遍历的某个位置，初始值为 <code>0</code>。<code>index</code> 对应的节点是「当前节点不断往左走达到的最终节点」，这也是符合中序遍历的，它的作用在下面的过程中会有所体现。</p> <p>首先我们将根节点 <code>3</code> 入栈，再初始化 <code>index</code> 所指向的节点为 <code>4</code>，随后对于前序遍历中的每个节点，我们依次判断它是栈顶节点的左儿子，还是栈中某个节点的右儿子。</p> <ul><li><p>我们遍历 <code>9</code>。<code>9</code> 一定是栈顶节点 <code>3</code> 的左儿子。我们使用反证法，假设 <code>9</code> 是 <code>3</code> 的右儿子，那么 <code>3</code> 没有左儿子，<code>index</code> 应该恰好指向 <code>3</code>，但实际上为 <code>4</code>，因此产生了矛盾。所以我们将 <code>9</code> 作为 <code>3</code> 的左儿子，并将 <code>9</code> 入栈。</p> <ul><li><code>stack = [3, 9]</code></li> <li><code>index -&gt; inorder[0] = 4</code></li></ul></li> <li><p>我们遍历 <code>8</code>，<code>5</code> 和 <code>4</code>。同理可得它们都是上一个节点（栈顶节点）的左儿子，所以它们会依次入栈。</p> <ul><li><code>stack = [3, 9, 8, 5, 4]</code></li> <li><code>index -&gt; inorder[0] = 4</code></li></ul></li> <li><p>我们遍历 <code>10</code>，这时情况就不一样了。我们发现 <code>index</code> 恰好指向当前的栈顶节点 <code>4</code>，也就是说 <code>4</code> 没有左儿子，那么 <code>10</code> 必须为栈中某个节点的右儿子。那么如何找到这个节点呢？栈中的节点的顺序和它们在前序遍历中出现的顺序是一致的，而且每一个节点的右儿子都还没有被遍历过，<strong>那么这些节点的顺序和它们在中序遍历中出现的顺序一定是相反的</strong>。</p> <blockquote><p>这是因为栈中的任意两个相邻的节点，前者都是后者的某个祖先。并且我们知道，栈中的任意一个节点的右儿子还没有被遍历过，说明后者一定是前者左儿子的子树中的节点，那么后者就先于前者出现在中序遍历中。</p></blockquote> <p>因此我们可以把 <code>index</code> 不断向右移动，并与栈顶节点进行比较。如果 <code>index</code> 对应的元素恰好等于栈顶节点，那么说明我们在中序遍历中找到了栈顶节点，所以将 <code>index</code> 增加 <code>1</code> 并弹出栈顶节点，直到 <code>index</code> 对应的元素不等于栈顶节点。按照这样的过程，我们弹出的最后一个节点 <code>x</code> 就是 <code>10</code> 的双亲节点，<strong>这是因为 <code>10</code> 出现在了 <code>x</code> 与 <code>x</code> 在栈中的下一个节点的中序遍历之间</strong>，因此 <code>10</code> 就是 <code>x</code> 的右儿子。</p> <p>回到我们的例子，我们会依次从栈顶弹出 <code>4</code>，<code>5</code> 和 <code>8</code>，并且将 <code>index</code> 向右移动了三次。我们将 <code>10</code> 作为最后弹出的节点 <code>8</code> 的右儿子，并将 <code>10</code> 入栈。</p> <ul><li><code>stack = [3, 9, 10]</code></li> <li><code>index -&gt; inorder[3] = 10</code></li></ul></li> <li><p>我们遍历 <code>20</code>。同理，<code>index</code> 恰好指向当前栈顶节点 <code>10</code>，那么我们会依次从栈顶弹出 <code>10</code>，<code>9</code> 和 <code>3</code>，并且将 <code>index</code> 向右移动了三次。我们将 <code>20</code> 作为最后弹出的节点 <code>3</code> 的右儿子，并将 <code>20</code> 入栈。</p> <ul><li><code>stack = [20]</code></li> <li><code>index -&gt; inorder[6] = 15</code></li></ul></li> <li><p>我们遍历 <code>15</code>，将 <code>15</code> 作为栈顶节点 <code>20</code> 的左儿子，并将 <code>15</code> 入栈。</p> <ul><li><code>stack = [20, 15]</code></li> <li><code>index -&gt; inorder[6] = 15</code></li></ul></li> <li><p>我们遍历 <code>7</code>。<code>index</code> 恰好指向当前栈顶节点 <code>15</code>，那么我们会依次从栈顶弹出 <code>15</code> 和 <code>20</code>，并且将 <code>index</code> 向右移动了两次。我们将 <code>7</code> 作为最后弹出的节点 <code>20</code> 的右儿子，并将 <code>7</code> 入栈。</p> <ul><li><code>stack = [7]</code></li> <li><code>index -&gt; inorder[8] = 7</code></li></ul></li></ul> <p>此时遍历结束，我们就构造出了正确的二叉树。</p> <p><strong>算法</strong></p> <p>我们归纳出上述例子中的算法流程：</p> <ul><li><p>我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；</p></li> <li><p>我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 <code>index</code> 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 <code>index</code>，并将当前节点作为最后一个弹出的节点的右儿子；如果 <code>index</code> 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；</p></li> <li><p>无论是哪一种情况，我们最后都将当前的节点入栈。</p></li></ul> <p>最后得到的二叉树即为答案。</p> <div class="language-C++ [sol2-C++] line-numbers-mode"><pre class="language-text"><code>class Solution {
public:
    TreeNode* buildTree(vector&lt;int&gt;&amp; preorder, vector&lt;int&gt;&amp; inorder) {
        if (!preorder.size()) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[0]);
        stack&lt;TreeNode*&gt; stk;
        stk.push(root);
        int inorderIndex = 0;
        for (int i = 1; i &lt; preorder.size(); ++i) {
            int preorderVal = preorder[i];
            TreeNode* node = stk.top();
            if (node-&gt;val != inorder[inorderIndex]) {
                node-&gt;left = new TreeNode(preorderVal);
                stk.push(node-&gt;left);
            }
            else {
                while (!stk.empty() &amp;&amp; stk.top()-&gt;val == inorder[inorderIndex]) {
                    node = stk.top();
                    stk.pop();
                    ++inorderIndex;
                }
                node-&gt;right = new TreeNode(preorderVal);
                stk.push(node-&gt;right);
            }
        }
        return root;
    }
};
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br></div></div><div class="language-Java [sol2-Java] line-numbers-mode"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">TreeNode</span> <span class="token function">buildTree</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> preorder<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> inorder<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>preorder <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> preorder<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token class-name">TreeNode</span> root <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>preorder<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">Deque</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">TreeNode</span><span class="token punctuation">&gt;</span></span> stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">TreeNode</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> inorderIndex <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> preorder<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> preorderVal <span class="token operator">=</span> preorder<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token class-name">TreeNode</span> node <span class="token operator">=</span> stack<span class="token punctuation">.</span><span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>val <span class="token operator">!=</span> inorder<span class="token punctuation">[</span>inorderIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>preorderVal<span class="token punctuation">)</span><span class="token punctuation">;</span>
                stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> stack<span class="token punctuation">.</span><span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>val <span class="token operator">==</span> inorder<span class="token punctuation">[</span>inorderIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    node <span class="token operator">=</span> stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                    inorderIndex<span class="token operator">++</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>preorderVal<span class="token punctuation">)</span><span class="token punctuation">;</span>
                stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> root<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br></div></div><div class="language-Python [sol2-Python3] line-numbers-mode"><pre class="language-python"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">buildTree</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> preorder<span class="token punctuation">:</span> List<span class="token punctuation">[</span><span class="token builtin">int</span><span class="token punctuation">]</span><span class="token punctuation">,</span> inorder<span class="token punctuation">:</span> List<span class="token punctuation">[</span><span class="token builtin">int</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">&gt;</span> TreeNode<span class="token punctuation">:</span>
        <span class="token keyword">if</span> <span class="token keyword">not</span> preorder<span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token boolean">None</span>

        root <span class="token operator">=</span> TreeNode<span class="token punctuation">(</span>preorder<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        stack <span class="token operator">=</span> <span class="token punctuation">[</span>root<span class="token punctuation">]</span>
        inorderIndex <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token builtin">len</span><span class="token punctuation">(</span>preorder<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            preorderVal <span class="token operator">=</span> preorder<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            node <span class="token operator">=</span> stack<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
            <span class="token keyword">if</span> node<span class="token punctuation">.</span>val <span class="token operator">!=</span> inorder<span class="token punctuation">[</span>inorderIndex<span class="token punctuation">]</span><span class="token punctuation">:</span>
                node<span class="token punctuation">.</span>left <span class="token operator">=</span> TreeNode<span class="token punctuation">(</span>preorderVal<span class="token punctuation">)</span>
                stack<span class="token punctuation">.</span>append<span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span>
            <span class="token keyword">else</span><span class="token punctuation">:</span>
                <span class="token keyword">while</span> stack <span class="token keyword">and</span> stack<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>val <span class="token operator">==</span> inorder<span class="token punctuation">[</span>inorderIndex<span class="token punctuation">]</span><span class="token punctuation">:</span>
                    node <span class="token operator">=</span> stack<span class="token punctuation">.</span>pop<span class="token punctuation">(</span><span class="token punctuation">)</span>
                    inorderIndex <span class="token operator">+=</span> <span class="token number">1</span>
                node<span class="token punctuation">.</span>right <span class="token operator">=</span> TreeNode<span class="token punctuation">(</span>preorderVal<span class="token punctuation">)</span>
                stack<span class="token punctuation">.</span>append<span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span>

        <span class="token keyword">return</span> root
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br></div></div><div class="language-golang [sol2-Golang] line-numbers-mode"><pre class="language-text"><code>func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &amp;TreeNode{preorder[0], nil, nil}
    stack := []*TreeNode{}
    stack = append(stack, root)
    var inorderIndex int
    for i := 1; i &lt; len(preorder); i++ {
        preorderVal := preorder[i]
        node := stack[len(stack)-1]
        if node.Val != inorder[inorderIndex] {
            node.Left = &amp;TreeNode{preorderVal, nil, nil}
            stack = append(stack, node.Left)
        } else {
            for len(stack) != 0 &amp;&amp; stack[len(stack)-1].Val == inorder[inorderIndex] {
                node = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                inorderIndex++
            }
            node.Right = &amp;TreeNode{preorderVal, nil, nil}
            stack = append(stack, node.Right)
        }
    }
    return root
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br></div></div><p><strong>复杂度分析</strong></p> <ul><li>时间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，其中 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 是树中的节点个数。</li> <li>空间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，除去返回的答案需要的 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 空间之外，我们还需要使用 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>（其中 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi></mjx-math></mjx-container> 是树的高度）的空间存储栈。这里 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="&lt;"></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>，所以（在最坏情况下）总空间复杂度为 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</li></ul> <h2 id="总结"><a href="#总结" class="header-anchor">#</a> 总结</h2> <p>「递归」方法虽然会有栈的开销，但是我们在面对一个复杂问题的时候，通过「拆分子问题」，解决「子问题」的方式往往会使得问题变得简单。因此编写「递归」方法或者说「分治思想」是我们解决问题的重要手段。</p> <h2 id="练习"><a href="#练习" class="header-anchor">#</a> 练习</h2> <ol><li>完成「力扣」第 106 题：从中序与后序遍历序列构造二叉树（中等）；</li> <li>完成「力扣」第 109 题：将有序数组转换为二叉搜索树（简单）；</li> <li>完成「力扣」第 98 题：验证二叉搜索树（中等）；</li> <li>完成「力扣」第 104 题：二叉树的最大深度（简单）；</li> <li>完成「力扣」第 110 题：平衡二叉树（简单）；</li> <li>完成「力扣」第 124 题：二叉树中的最大路径和（困难）；</li> <li>完成「力扣」第 199 题：二叉树的右视图（中等）。</li></ol></div> <footer class="page-edit"><!----> <!----></footer> <!----> </main></div><div class="global-ui"><!----></div></div>
    <script src="/book/assets/js/app.a4355b0d.js" defer></script><script src="/book/assets/js/2.ba785ee6.js" defer></script><script src="/book/assets/js/32.aac9aa62.js" defer></script>
  </body>
</html>
